SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Sparse approximation</title>

</head>

Sparse approximation

</h1>

</header>

Sparse approximation (also known as sparse representation) theory deals with <a href="Sparsity" class="mw-redirect" title="Sparsity">sparse</a> solutions for <a href="System_of_linear_equations" title="System of linear equations">systems of linear equations</a>. Techniques for finding these solutions and exploiting them in applications have found wide use in <a href="Image_processing" class="mw-redirect" title="Image processing">image processing</a>, <a href="Signal_processing" title="Signal processing">signal processing</a>, <a href="Machine_learning" title="Machine learning">machine learning</a>, <a href="Medical_imaging" title="Medical imaging">medical imaging</a>, and more.

<div class="mw-heading mw-heading2"><h2 id="Sparse_decomposition">Sparse decomposition</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Noiseless_observations">Noiseless observations</h3></div>

Consider a <a href="System_of_linear_equations" title="System of linear equations">linear system of equations</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=D\alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=D\alpha }</annotation>

</semantics>

</math><img src="./cd4b0ed8c1f3495bcedfdcf96647f58ce346da82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.84ex; height:2.176ex;" alt="{\displaystyle x=D\alpha }" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> is an <a href="Underdetermined_system" title="Underdetermined system">underdetermined</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\times p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\times p}</annotation>

</semantics>

</math><img src="./5e459f087ef822dc6fba54b953c60de61be69c42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.05ex; height:2.009ex;" alt="{\displaystyle m\times p}" loading="lazy"> <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (m<p)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (m<p)}</annotation>

</semantics>

</math><img src="./27bc84d9985e171e9621dae82dfbe6f409685e48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.118ex; height:2.843ex;" alt="{\displaystyle (m<p)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}}</annotation>

</semantics>

</math><img src="./9d6c2eec021a27b383c2f81ec890bfa0b04166ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.623ex; height:2.676ex;" alt="{\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}}" loading="lazy">. The matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> (typically assumed to be full-rank) is referred to as the dictionary, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is a signal of interest. The core sparse representation problem is defined as the quest for the sparsest possible representation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> satisfying <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=D\alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=D\alpha }</annotation>

</semantics>

</math><img src="./cd4b0ed8c1f3495bcedfdcf96647f58ce346da82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.84ex; height:2.176ex;" alt="{\displaystyle x=D\alpha }" loading="lazy">. Due to the underdetermined nature of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy">, this linear system admits in general infinitely many possible solutions, and among these we seek the one with the fewest non-zeros. Put formally, we solve

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mtext> subject to </mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}x=D\alpha ,}</annotation>

</semantics>

</math><img src="./56f63fbfb925e090711760e699737c2ed23864bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:28.903ex; height:4.176ex;" alt="{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}x=D\alpha ,}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}}</annotation>

</semantics>

</math><img src="./0c5688522938b32ede541f26551493e43a7cf537.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.346ex; height:2.843ex;" alt="{\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}}" loading="lazy"> is the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> pseudo-norm, which counts the <a href="Cardinality" title="Cardinality">number</a> of non-zero components of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy">. This problem is known to be NP-hard with a reduction to NP-complete subset selection problems in <a href="Combinatorial_optimization" title="Combinatorial optimization">combinatorial optimization</a>.

Sparsity of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> implies that only a few (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\ll m<p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\ll m<p}</annotation>

</semantics>

</math><img src="./e78b24333c769dc0c4b8867747fe8c83fda03965.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.134ex; height:2.509ex;" alt="{\displaystyle k\ll m<p}" loading="lazy">) components in it are non-zero. The underlying motivation for such a sparse decomposition is the desire to provide the simplest possible explanation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> as a linear combination of as few as possible columns from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy">, also referred to as atoms. As such, the signal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> can be viewed as a molecule composed of a few fundamental elements taken from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy">.

While the above posed problem is indeed NP-Hard, its solution can often be found using approximation algorithms. One such option is a convex <a href="Relaxation_(approximation)" title="Relaxation (approximation)">relaxation</a> of the problem, obtained by using the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy">-norm instead of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|\alpha \|_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|\alpha \|_{1}}</annotation>

</semantics>

</math><img src="./d6118190790c976527c88cbd08a361103f59a8e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.867ex; height:2.843ex;" alt="{\displaystyle \|\alpha \|_{1}}" loading="lazy"> simply sums the absolute values of the entries in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy">. This is known as the <a href="Basis_pursuit" title="Basis pursuit">basis pursuit</a> (BP) algorithm, which can be handled using any <a href="Linear_programming" title="Linear programming">linear programming</a> solver. An alternative approximation method is a greedy technique, such as the <a href="Matching_pursuit" title="Matching pursuit">matching pursuit</a> (MP), which finds the location of the non-zeros one at a time.

Surprisingly, under mild conditions on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> (using the <a href="Spark_(mathematics)" title="Spark (mathematics)">spark (mathematics)</a>, the <a href="Mutual_coherence_(linear_algebra)" title="Mutual coherence (linear algebra)">mutual coherence</a> or the <a href="Restricted_isometry_property" title="Restricted isometry property">restricted isometry property</a>) and the level of sparsity in the solution, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, the sparse representation problem can be shown to have a unique solution, and BP and MP are guaranteed to find it perfectly.<a href="#cite_note-donohoelad2003-1">[1]</a><a href="#cite_note-Tropp2004-2">[2]</a><a href="#cite_note-donoho2006most-3">[3]</a>

<div class="mw-heading mw-heading3"><h3 id="Noisy_observations">Noisy observations</h3></div>

Often the observed signal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is noisy. By relaxing the equality constraint and imposing an <a href="L2_norm" class="mw-redirect" title="L2 norm"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{2}}</annotation>

</semantics>

</math><img src="./85a4571ee9be10bd3c9df2480ab3d280f99e801a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{2}}" loading="lazy"></a>-norm on the data-fitting term, the sparse decomposition problem becomes

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mtext> subject to </mtext>

</mrow>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2},}</annotation>

</semantics>

</math><img src="./6dd1d0c169ad57fc19d8b4114dbfa01ffbae029c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:37.121ex; height:4.509ex;" alt="{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2},}" loading="lazy"></dd></dl>

or put in a Lagrangian form,

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{0}+{\frac {1}{2}}\|x-D\alpha \|_{2}^{2},}</annotation>

</semantics>

</math><img src="./73e73a3cd906546fb34857b55475a5a07b6acbbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:27.226ex; height:5.509ex;" alt="{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{0}+{\frac {1}{2}}\|x-D\alpha \|_{2}^{2},}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation>

</semantics>

</math><img src="./b43d0ea3c9c025af1be9128e62a18fa74bedda2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }" loading="lazy"> is replacing the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy">.

Just as in the noiseless case, these two problems are NP-Hard in general, but can be approximated using pursuit algorithms. More specifically, changing the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> to an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy">-norm, we obtain

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{1}+{\frac {1}{2}}\|x-D\alpha \|_{2}^{2},}</annotation>

</semantics>

</math><img src="./fff75448daebfa98836c1f639e6b49c776d3c43c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:27.226ex; height:5.509ex;" alt="{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{1}+{\frac {1}{2}}\|x-D\alpha \|_{2}^{2},}" loading="lazy"></dd></dl>

which is known as the <a href="Basis_pursuit_denoising" title="Basis pursuit denoising">basis pursuit denoising</a>. Similarly, <a href="Matching_pursuit" title="Matching pursuit">matching pursuit</a> can be used for approximating the solution of the above problems, finding the locations of the non-zeros one at a time until the error threshold is met. Here as well, theoretical guarantees suggest that BP and MP lead to nearly optimal solutions depending on the properties of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> and the cardinality of the solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">.

Another interesting theoretical result refers to the case in which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> is a <a href="Unitary_matrix" title="Unitary matrix">unitary matrix</a>. Under this assumption, the problems posed above (with either <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy">) admit closed-form solutions in the form of non-linear shrinkage.<a href="#cite_note-Elad2010-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Variations">Variations</h2></div>

There are several variations to the basic sparse approximation problem.

Structured sparsity: In the original version of the problem, any of the atoms in the dictionary can be picked. In the structured (block) sparsity model, instead of picking atoms individually, groups of them are to be picked. These groups can be overlapping and of varying size. The objective is to represent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> such that it is sparse while forcing this block-structure.<a href="#cite_note-7">[7]</a>

Collaborative (joint) sparse coding: The original version of the problem is defined for a single signal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. In the collaborative (joint) sparse coding model, a set of signals is available, each believed to emerge from (nearly) the same set of atoms from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy">. In this case, the pursuit task aims to recover a set of sparse representations that best describe the data while forcing them to share the same (or close-by) support.<a href="#cite_note-8">[8]</a>

Other structures: More broadly, the sparse approximation problem can be cast while forcing a specific desired structure on the pattern of non-zero locations in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy">. Two cases of interest that have been extensively studied are tree-based structure, and more generally, a Boltzmann distributed support.<a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

As already mentioned above, there are various approximation (also referred to as pursuit) algorithms that have been developed for addressing the sparse representation problem:

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mtext> subject to </mtext>

</mrow>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2}.}</annotation>

</semantics>

</math><img src="./e03cd25694088c36e5671efbc3cd43e2c54d247e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:37.121ex; height:4.509ex;" alt="{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2}.}" loading="lazy"></dd></dl>

We mention below a few of these main methods.

<ul><li><a href="Matching_pursuit" title="Matching pursuit">Matching pursuit</a> is a greedy iterative algorithm for approximately solving the above problem. It works by gradually finding the locations of the non-zeros in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> one at a time. The core idea is to find in each step the column (atom) in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> that best correlates with the current residual (initialized to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">), and then updating this residual to take the new atom and its coefficient into account. Matching pursuit might pick the same atom multiple times.</li>

<li>Orthogonal matching pursuit is very similar to matching pursuit, with one major difference: in each of the algorithm's step, all the non-zero coefficients are updated by a <a href="Least_squares" title="Least squares">least squares</a>. As a consequence, the residual is orthogonal to the already chosen atoms, and thus an atom cannot be picked more than once.</li>

<li>Stage-wise greedy methods: Improved variations over the above are algorithms that operate greedily while adding two critical features: (i) the ability to add groups of non-zeros at a time (instead of one non-zero per round); and (ii) including a pruning step in each round in which several of the atoms are discarded from the support. Representatives of this approach are the Subspace-Pursuit algorithm and the CoSaMP.<a href="#cite_note-10">[10]</a></li></ul>

<ul><li><a href="Basis_pursuit_denoising" title="Basis pursuit denoising">Basis pursuit</a> solves a convex relaxed version of the problem by replacing the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> by an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy">-norm. Note that this only defines a new objective, while leaving open the question of the algorithm to use for getting the desired solution. Commonly considered such algorithms are the <a href="Iteratively_reweighted_least_squares" title="Iteratively reweighted least squares">IRLS</a>, <a href="Least-angle_regression" title="Least-angle regression">LARS</a>, and iterative soft-shrinkage methods.<a href="#cite_note-11">[11]</a></li></ul>

<ul><li>There are several other methods for solving sparse decomposition problems: homotopy method, <a href="Coordinate_descent" title="Coordinate descent">coordinate descent</a>, iterative hard-thresholding, first order <a href="Proximal_gradient_method" title="Proximal gradient method">proximal methods</a>, which are related to the above-mentioned iterative soft-shrinkage algorithms, and Dantzig selector.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Sparse approximation ideas and algorithms have been extensively used in <a href="Signal_processing" title="Signal processing">signal processing</a>, <a href="Image_processing" class="mw-redirect" title="Image processing">image processing</a>, <a href="Machine_learning" title="Machine learning">machine learning</a>, <a href="Medical_imaging" title="Medical imaging">medical imaging</a>, <a href="Array_processing" title="Array processing">array processing</a>, <a href="Data_mining" title="Data mining">data mining</a>, and more. In most of these applications, the unknown signal of interest is modeled as a sparse combination of a few atoms from a given dictionary, and this is used as the <a href="Regularization_(mathematics)" title="Regularization (mathematics)">regularization</a> of the problem. These problems are typically accompanied by a <a href="Dictionary_learning" class="mw-redirect" title="Dictionary learning">dictionary learning</a> mechanism that aims to fit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> to best match the model to the given data. The use of sparsity-inspired models has led to state-of-the-art results in a wide set of applications.<a href="#cite_note-survey1-12">[12]</a><a href="#cite_note-survey2-13">[13]</a><a href="#cite_note-survey3-14">[14]</a> Recent work suggests that there is a tight connection between sparse representation modeling and deep-learning.<a href="#cite_note-deeplearning-15">[15]</a>

<ul><li><a href="Compressed_sensing" title="Compressed sensing">Compressed sensing</a></li>

<li><a href="Sparse_dictionary_learning" title="Sparse dictionary learning">Sparse dictionary learning</a></li>

<li><a href="Lasso_(statistics)" title="Lasso (statistics)">Lasso (statistics)</a></li>

<li><a href="Regularization_(mathematics)" title="Regularization (mathematics)">Regularization (mathematics)</a> and <a href="Inverse_problems" class="mw-redirect" title="Inverse problems">inverse problems</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDonoho,_D.L._and_Elad,_M.2003" class="citation journal cs1">Donoho, D.L. and Elad, M. (2003). <a rel="nofollow" class="external text" href="https://www.cs.technion.ac.il/~elad/publications/journals/2003/15_New_Sparseness_IT.pdf">"Optimally sparse representation in general (nonorthogonal) dictionaries via L1 minimization"</a> (PDF). Proceedings of the National Academy of Sciences. 100 (5): 2197–2202. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2003PNAS..100.2197D">2003PNAS..100.2197D</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1073%2Fpnas.0437847100">10.1073/pnas.0437847100</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC153464">153464</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/16576749">16576749</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-Tropp2004-2"><a href="#cite_ref-Tropp2004_2-0">^</a> <cite id="CITEREFTropp,_J.A.2004" class="citation journal cs1">Tropp, J.A. (2004). <a rel="nofollow" class="external text" href="https://authors.library.caltech.edu/9035/1/TROieeetit04a.pdf">"Greed is good: Algorithmic results for sparse approximation"</a> (PDF). IEEE Transactions on Information Theory. 50 (10): 2231–2242. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.321.1443">10.1.1.321.1443</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2004.834793">10.1109/TIT.2004.834793</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:675692">675692</a>.</cite>

</li>

<li id="cite_note-donoho2006most-3"><a href="#cite_ref-donoho2006most_3-0">^</a> <cite id="CITEREFDonoho,_D.L.2006" class="citation journal cs1">Donoho, D.L. (2006). <a rel="nofollow" class="external text" href="http://www-stat.stanford.edu/~donoho/Reports/2004/l1l0approx.pdf">"For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution"</a> (PDF). Communications on Pure and Applied Mathematics. 56 (6): 797–829. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fcpa.20132">10.1002/cpa.20132</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8510060">8510060</a>.</cite>

</li>

<li id="cite_note-Elad2010-4">^ <a href="#cite_ref-Elad2010_4-0">a</a> <a href="#cite_ref-Elad2010_4-1">b</a> <cite id="CITEREFElad,_M.2010" class="citation book cs1">Elad, M. (2010). Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.331.8963">10.1.1.331.8963</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4419-7011-4">10.1007/978-1-4419-7011-4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1441970107</bdi>.</cite>

</li>

<li id="cite_note-DonohoEladTem2006-5"><a href="#cite_ref-DonohoEladTem2006_5-0">^</a> <cite id="CITEREFDonoho,_D.L.,_Elad,_M._and_Templyakov,_V.2006" class="citation journal cs1">Donoho, D.L., Elad, M. and Templyakov, V. (2006). <a rel="nofollow" class="external text" href="https://www.cs.technion.ac.il/~elad/publications/journals/2004/23_Stability_IEEE_TIT.pdf">"Stable recovery of sparse overcomplete representations in the presence of noise"</a> (PDF). IEEE Transactions on Information Theory. 52 (1): 6–18. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.5610">10.1.1.125.5610</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2005.860430">10.1109/TIT.2005.860430</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14813938">14813938</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-Tropp2006-6"><a href="#cite_ref-Tropp2006_6-0">^</a> <cite id="CITEREFTropp,_J.A.2006" class="citation journal cs1">Tropp, J.A. (2006). <a rel="nofollow" class="external text" href="https://authors.library.caltech.edu/9040/1/TROieeetit06.pdf">"Just relax: Convex programming methods for identifying sparse signals in noise"</a> (PDF). IEEE Transactions on Information Theory. 52 (3): 1030–1051. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.184.2957">10.1.1.184.2957</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2005.864420">10.1109/TIT.2005.864420</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6496872">6496872</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFEldar,_Y.C,_Kuppinger,_P._and_Bolcskei,_H.2009" class="citation journal cs1">Eldar, Y.C, Kuppinger, P. and Bolcskei, H. (2009). "Block-sparse signals: Uncertainty relations and efficient recovery". IEEE Transactions on Signal Processing. 58 (6): 3042–3054. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0906.3173">0906.3173</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2010ITSP...58.3042E">2010ITSP...58.3042E</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTSP.2010.2044837">10.1109/TSP.2010.2044837</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:335122">335122</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFTropp,_J.A.,_Gilbert,_A.C._and_Strauss,_M.J.2006" class="citation journal cs1">Tropp, J.A., Gilbert, A.C. and Strauss, M.J. (2006). "Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit". Signal Processing. 86 (3): 572–588. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.sigpro.2005.05.030">10.1016/j.sigpro.2005.05.030</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFPeleg,_T._Eldar,_Y.C._and_Elad,_M.2012" class="citation journal cs1">Peleg, T. Eldar, Y.C. and Elad, M. (2012). "Exploiting Statistical Dependencies in Sparse Representations for Signal Recovery". IEEE Transactions on Signal Processing. 60 (5): 2286–2303. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1010.5734">1010.5734</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2012ITSP...60.2286P">2012ITSP...60.2286P</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTSP.2012.2188520">10.1109/TSP.2012.2188520</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3179803">3179803</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFNeedell,_D._and_Tropp,_J.A.2009" class="citation journal cs1">Needell, D. and Tropp, J.A. (2009). "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples". Applied and Computational Harmonic Analysis. 26 (3): 301–321. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0803.2392">0803.2392</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.acha.2008.07.002">10.1016/j.acha.2008.07.002</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFZibulevsky,_M._and_Elad,_M.2010" class="citation journal cs1">Zibulevsky, M. and Elad, M. (2010). <a rel="nofollow" class="external text" href="https://www.cs.technion.ac.il/~elad/publications/journals/2010/L1L2_IEEE_SPM_2010.pdf">"L1-L2 optimization in signal and image processing"</a> (PDF). IEEE Signal Processing Magazine. 27 (3): 76–88. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2010ISPM...27...76Z">2010ISPM...27...76Z</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FMSP.2010.936023">10.1109/MSP.2010.936023</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2783691">2783691</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-survey1-12"><a href="#cite_ref-survey1_12-0">^</a> <cite id="CITEREFBaraniuk,_R.G._Candes,_E._Elad,_M._and_Ma,_Y.2010" class="citation journal cs1">Baraniuk, R.G. Candes, E. Elad, M. and Ma, Y. (2010). "Applications of sparse representation and compressive sensing". Proceedings of the IEEE. 98 (6): 906–909. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJPROC.2010.2047424">10.1109/JPROC.2010.2047424</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-survey2-13"><a href="#cite_ref-survey2_13-0">^</a> <cite id="CITEREFElad,_M._Figueiredo,_M.A.T.,_and_Ma,_Y.2010" class="citation journal cs1">Elad, M. Figueiredo, M.A.T., and Ma, Y. (2010). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180117070225/https://pdfs.semanticscholar.org/5393/46f7f35f83875d9e86851010ee35d1a47e69.pdf">"On the role of sparse and redundant representations in image processing"</a> (PDF). Proceedings of the IEEE. 98 (6): 972–982. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.465">10.1.1.160.465</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJPROC.2009.2037655">10.1109/JPROC.2009.2037655</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10992685">10992685</a>. Archived from <a rel="nofollow" class="external text" href="https://pdfs.semanticscholar.org/5393/46f7f35f83875d9e86851010ee35d1a47e69.pdf">the original</a> (PDF) on 2018-01-17.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-survey3-14"><a href="#cite_ref-survey3_14-0">^</a> <cite id="CITEREFPlumbley,_M.D._Blumensath,_T._Daudet,_L._Gribonval,_R._and_Davies,_M.E.2010" class="citation journal cs1">Plumbley, M.D. Blumensath, T. Daudet, L. Gribonval, R. and Davies, M.E. (2010). "Sparse representations in audio and music: From coding to source separation". Proceedings of the IEEE. 98 (6): 995–1005. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.1607">10.1.1.160.1607</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJPROC.2009.2030345">10.1109/JPROC.2009.2030345</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:4461063">4461063</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-deeplearning-15"><a href="#cite_ref-deeplearning_15-0">^</a> <cite id="CITEREFPapyan,_V._Romano,_Y._and_Elad,_M.2017" class="citation journal cs1">Papyan, V. Romano, Y. and Elad, M. (2017). <a rel="nofollow" class="external text" href="http://jmlr.org/papers/volume18/16-505/16-505.pdf">"Convolutional Neural Networks Analyzed via Convolutional Sparse Coding"</a> (PDF). Journal of Machine Learning Research. 18 (83): 1–52. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1607.08194">1607.08194</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2016arXiv160708194P">2016arXiv160708194P</a>.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)

</li>

</ol></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Numerical_linear_algebra64" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Numerical_linear_algebra64" style="font-size:114%;margin:0 4em"><a href="Numerical_linear_algebra" title="Numerical linear algebra">Numerical linear algebra</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Key concepts</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Floating_point" class="mw-redirect" title="Floating point">Floating point</a></li>

<li><a href="Numerical_stability" title="Numerical stability">Numerical stability</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Problems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="System_of_linear_equations" title="System of linear equations">System of linear equations</a></li>

<li><a href="Matrix_decomposition" title="Matrix decomposition">Matrix decompositions</a></li>

<li><a href="Matrix_multiplication" title="Matrix multiplication">Matrix multiplication</a> (<a href="Matrix_multiplication_algorithm" title="Matrix multiplication algorithm">algorithms</a>)</li>

<li><a href="Matrix_splitting" title="Matrix splitting">Matrix splitting</a></li>

<li><a href="Sparse_matrix" title="Sparse matrix">Sparse problems</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Hardware</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="CPU_cache" title="CPU cache">CPU cache</a></li>

<li><a href="Cache-oblivious_algorithm" title="Cache-oblivious algorithm">Cache-oblivious algorithm</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Software</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatically_Tuned_Linear_Algebra_Software" title="Automatically Tuned Linear Algebra Software">ATLAS</a></li>

<li><a href="MATLAB" title="MATLAB">MATLAB</a></li>

<li><a href="Basic_Linear_Algebra_Subprograms" title="Basic Linear Algebra Subprograms">Basic Linear Algebra Subprograms (BLAS)</a></li>

<li><a href="LAPACK" title="LAPACK">LAPACK</a></li>

<li><a href="Comparison_of_linear_algebra_libraries" title="Comparison of linear algebra libraries">Specialized libraries</a></li>

<li><a href="Comparison_of_numerical-analysis_software" title="Comparison of numerical-analysis software">General purpose software</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-11" href="https://en.wikipedia.org/wiki/?title=Sparse_approximation&oldid=1299899143">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>